1. Field of the Invention
The present invention relates to communication systems that encode and decode with concatenated codes, and, more particularly, to iterative decoding of data detected from a communication medium.
2. Description of the Related Art
Concatenated code systems for encoding and decoding data use two or more component codes that are concatenated during the process of encoding the data. Although the component codes may be of any type, the component codes are typically relatively simple codes such as the convolutional codes. The two or more component codes are concatenated either in serial or in parallel. For example, in serial concatenation of two component codes, data is first encoded by a first encoding module with a first component code. This encoded data is, in turn, passed through an interleaver and then applied to a second encoding module for encoding with a second component code. This process operates on only a single, serial data stream, and the first and second component codes may be the same code. In the parallel concatenation, in one processing path data is encoded with the first component code and in the other processing path data is interleaved and then is encoded with a second component code. The two encoded streams are combined in parallel by, for example, interleaving to provide a single encoded data stream.
For either serial or parallel concatenation, the encoded data is then used to modulate a signal that is passed through a communication (transmission) channel to a receiver, which processes the transmitted signal from the transmission channel. Such transmission channel may correspond to recording on and playback from a magnetic medium, or may correspond to transmission between users through a cellular/wireless/wired channel. The transmission channel has a corresponding frequency response that possibly includes memory (e.g., a partial response channel). The signal modulated by the encoded data has an added noise component and added signal distortion caused by the channel""s frequency response as the signal passes through the transmission channel.
The term xe2x80x9coutput channel samplexe2x80x9d refers to the samples of the channel output (signal modulated by encoded data) from the transmission channel that is generated through the sampling process of the receiver. The receiver typically includes a detector to detect the sequence of symbol bits representing the encoded data from the output channel samples. A decoder receives the detected symbol sequence from the detector and decodes the sequence of symbol bits o reconstruct the data. The decoder may be a simple decoder reversing the encoding process, or it may be an iterative decoder that repetitively decodes the data for a predefined number of iterations or until a predetermined decoding metric, such as maintaining the bit-error rate (BER), is less than a specified threshold.
The detector and the decoder may each typically employ a partial-response, maximum-likelihood (PRML) algorithm (e.g., a Viterbi algorithm (VA)), a maximum a posteriori (MAP) algorithm, or a soft-output Viterbi algorithm (SOVA). SOVA algorithms are known in the art and is described in, for example, J. Hagenauer and P. Hoeher, xe2x80x9cA Viterbi Algorithm With Soft Decision Outputs and Its Applications,xe2x80x9d Proc. of IEEE Globecom ""89, pp. 1680-1686, November, 1989, the teachings of which are incorporated herein by reference.
Concatenated code systems may employ iterative decoding of encoded data using either serial or parallel iterative decoding methods. When employing iterative decoding of data encoded with a concatenated code, a block of data is input to the iterative decoder. The block boundaries desirably conform to symbol boundaries of the concatenated code. The iterative decoder may comprise N component code decoders for decoding in accordance with each of the N component codes originally used to encode the data. The particular implementation of the iterative decoder is dependent on whether the encoding process was based on serial or parallel concatenation.
In an iterative decoding method, the complete decoding process during each iteration subjects a block of encoded data to decoding by each of the N component code decoders. The complete decoding process repeats for each iteration until a predetermined number (I) of decoding iterations are complete. Each iteration performs a complete, xe2x80x9csoftxe2x80x9d decoding of the data encoded with a concatenated code (i.e., a decoding with each component code of the concatenated code). Each iteration allows for higher confidence in the decisions for bits in the decoded data that are made based on the soft-output values provided from the detector.
The following definitions may be of use to understanding the encoding and decoding methods. A set of binary values U is defined in the Galois field-2 (GF(2)) with elements {+1, xe2x88x921} where xe2x88x921 is the xe2x80x9cnullxe2x80x9d element under ⊕ addition. The reliability value L(u) is the log-likelihood ratio of the binary random values in U and is defined as the natural log of the ratio of the probability that the random variable U takes on the value u=+1 to the probability that the random variable U takes on the value u=xe2x88x921. The sign of L(u) is used as a hard decision by a detector, and the magnitude of L(u) is used as a reliability statistic for the hard decision.
In an iterative decoding scheme, the reliability values for decoded user bits are updated at each iteration, utilizing the information extracted from the previous iteration, termed xe2x80x9csoft-in, soft-outxe2x80x9d decoding. Iterative decoding of concatenated codes using xe2x80x9csoft-in, soft-outxe2x80x9d information is well known in the art and is described in, for example, J. Hagenauer, E. Offer, and L. Papke, xe2x80x9cIterative Decoding of Block and Convolutional Codesxe2x80x9d, IEEE Transactions on Information Theory, Vol. 42, No. 2, March 1996, whose teachings are incorporated herein by reference.
To decode a block of output channel samples to provide a block of decoded data, the soft-in, soft-out decoder receives the output channel sample values from a transmission channel as well as a priori reliability values Lxe2x80x2(u) for the information bits u. The a priori reliability values Lxe2x80x2(u) may be 0 for the first iteration, and, after the first iteration, the soft decision (a posteriori) reliability values L(u) for the information bits from the previous iteration. Also provided are xe2x80x9cextrinsicxe2x80x9d values Le(u) for the decoded information bits. The xe2x80x9cextrinsicxe2x80x9d values Le(u) may be values based on indirect information not available from a previous iteration (e.g., other parity bits added to the information bits or the values from decoding with one component code that are subsequently used to make a hard decision for an information bit when decoding with another component code. For each decoding iteration in the 2-dimensional case, the decoder completes a decoding operation for each component code. In this case, the extrinsic values Le(u) may be employed sequentially as a priori reliability values Lxe2x80x2(u) for soft-in, soft-out decoding of each component code.
When concatenated codes are used to encode data that is then passed through a transmission channel with memory, additional decoding (performance) gain is achieved when each iteration of decoding also includes full demodulation of the received data. Full demodulation refers to complete detection of a block of symbols from the output channel samples before subjecting the block of symbols to an iteration of decoding. This is commonly termed a xe2x80x9cfull-iterationxe2x80x9d decoding scheme because, in effect, iterative detection also takes place in the receiver. The full iterative decoder may be implemented as a serial iterative decoder that operates sequentially with I iterations. While MAP detectors achieve optimum performance, they are complex to implement, adding considerably to the complexity of iterative decoders. Consequently, for each iteration, detectors of the prior art typically employ a soft output Viterbi algorithm (SOVA) detector generating soft-output values for detected symbols from the output channel samples since the SOVA algorithm is less complex to implement in, for example, an integrated circuit (IC). The particular form of the SOVA algorithm used by the detector is based on the impulse response of the transmission channel.
An implementation of serial full-iteration decoding of the prior art is shown in FIG. 1 and applies I iterations of the decoding process on each block of output channel samples. A new block of output channel samples is applied to SOVA detector 101(1), which generates soft-output values. The soft-output values are then provided to decoder 102(1), which decodes the soft-output values to complete a first iteration of decoding. For the second iteration of decoding, the output of decoder 102(1) and the original output channel samples are provided to SOVA detector 101(2), which generates a new set of soft-output values. Since the decoding process itself may correct errors from incorrectly detected symbols, the output of the decoder may be used to evaluate the decisions for detected symbols, which may be reflected in updated reliability values of the detected sequence. The new set of soft-output values are provided to decoder 102(2), which decodes the new set of soft-output values to complete the second decoding iteration.
A fully decoded block is provided as data from the Ith decoding module 102(I), corresponding to the Ith decoding iteration. For a circuit implementation, a single SOVA detector and a single decoder may be employed using feedback from the output of the decoder back to the input of the SOVA detector. The iterative decoder then completes I iterations through an initial detection and decoding step followed by (Ixe2x88x921) steps of detection and decoding with soft-output decoded data from the feedback path.
The present invention relates to iterative decoding in which reliability values for detected data are updated with each iteration of decoding. For a first iteration, detected values for detected data may be generated by a soft-output Viterbi algorithm (SOVA) using a Viterbi detector and a post-processor. The reliability values are then used to decode during the first iteration. For each subsequent iteration, the post-processor is used to update the reliability values without the Viterbi detector before decoding. Employing a post-processor rather than implementing a full SOVA algorithm for each subsequent iteration may provide for, for example, reduced circuit area and complexity in an iterative decoder.
In accordance with an embodiment of the present invention, in a signal processing application, an iterative decoder decodes user data encoded with a concatenated code. The iterative decoder comprises a soft-output detector; and at least one post-processor and decoder pair. In a first-iteration, the soft-output detector generates, from output channel samples, soft-output values corresponding to decisions for the encoded user data; the post-processor of a first pair updates a set of reliability values corresponding to the decisions for the encoded user data based on the decisions and the output channel samples; and the decoder of the first pair decodes the set of soft-output values to provide decisions for decoded user data. In a subsequent iteration, the post-processor of a pair updates the set of reliability values to form a new set of soft-output values; and the decoder of the pair decodes the new set of soft-output values to provide new decisions for the decoded user data.